import java.util.ArrayList;
import java.util.PriorityQueue;
import java.util.Stack;

public class Main {

    public static ListNode reverseKGroup (ListNode head, int k) {
        // write code here
        //先创建一个虚拟的头节点
        if(head == null){
            return null;
        }
        //计算链表长度，如果长度小于分组，则直接返回头节点
        ListNode cur2=head;
        int len=0;
        while(cur2!=null){
            cur2=cur2.next;
            len++;
        }
        if(len < k || len==1){
            return head;
        }
        int c=len%k;//走几趟
        ListNode vhead=null;
        int time=1;
        //用一个大小为k的栈存储节点
        Stack<ListNode> stack=new Stack<>();
        ListNode cur=head;
        ListNode popNode=new ListNode(-1);//用于弹出时
        while(cur!=null && cur.next != null && len!=c){
            //讲k个节点放入stack中
            for(int i=k;i>0;i--){
                ListNode curNext=cur.next;
                cur.next=null;
                stack.push(cur);
                cur=curNext;
                len--;
            }
            //将stack中的节点拿出来

            while(!stack.isEmpty()){

                popNode.next=stack.pop();
                if(time ==1){
                    vhead=popNode.next;
                    time--;
                }
                popNode=popNode.next;
            }

        }
        if(cur != null){
            popNode.next=cur;
        }

        return vhead;
    }


    public static void main(String[] args) {
        ListNode vhead=new ListNode(-1);
        vhead=vhead.build();
        ListNode head=reverseKGroup(vhead,3);
        System.out.println(head);
    }


}